/**
 * 
 */
package string;

/**
 * @author Michael
 * The count-and-say sequence is the sequence of integers beginning as follows:
 * 1, 11, 21, 1211, 111221, ...
 * 1 is read off as "one 1" or 11.
 * 11 is read off as "two 1s" or 21.
 * 21 is read off as "one 2, then one 1" or 1211.
 */
public class CountAndSay {

	/**
	Mar 6 '12988 / 2561

	The count-and-say sequence is the sequence of integers beginning as follows:
	1, 11, 21, 1211, 111221, ...

	1 is read off as "one 1" or 11.
	11 is read off as "two 1s" or 21.
	21 is read off as "one 2, then one 1" or 1211.

	Given an integer n, generate the nth sequence.

	Note: The sequence of integers will be represented as a string.
	 */
	public String countAndSay(int n) {
		// Start typing your Java solution below
		// DO NOT write main() function
		String result = "1";

		for (int i = 1; i < n; i++) {
			char number = result.charAt(0);
			int counter = 1;
			StringBuilder sb = new StringBuilder();
			for (int j = 1; j < result.length(); j++) {
				if (result.charAt(j) == number) {
					counter++;
				} else {
					sb.append(counter).append(number);
					counter = 1;
					number = result.charAt(j);
				}
			}
			sb.append(counter).append(number);
			result = sb.toString();
		}

		return result;
	}

	/**
	 * 
	 */
	public CountAndSay() {
		// TODO Auto-generated constructor stub
	}

	public String countAndSayOld(int n) {
		assert (n > 0);
		String result = "1";

		for (int i = 1; i < n; ++i) {
			char number = result.charAt(0);
			int count = 1;
			StringBuilder sb = new StringBuilder();
			for (int j = 1; j < result.length(); ++j) {
				if (result.charAt(j) == number) {
					++count;
				} else {
					sb.append(count).append(number);
					number = result.charAt(j);
					count = 1;
				}
			}
			sb.append(count).append(number);
			result = sb.toString();
		}

		return result;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		CountAndSay cas = new CountAndSay();
		for (int i = 1; i < 30; i++) {
			System.out.printf("Count and Say :%d is %s\n", i,
					cas.countAndSay(i));
		}

	}
}
